import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
//递归
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetric(root.left, root.right);
    }

    boolean isSymmetric(TreeNode rootL, TreeNode rootR) {
        if (rootL == null || rootR == null) {
            return rootL == null && rootR == null;
        }

        if (rootL.val != rootR.val) {
            return false;
        }

        return isSymmetric(rootL.left, rootR.right) && isSymmetric(rootL.right, rootR.left);
    }
}

//迭代，两个队列层序遍历
class Solution1 {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }

        Queue<TreeNode> queueL = new ArrayDeque<>();
        Queue<TreeNode> queueR = new ArrayDeque<>();
        if (root.left == null || root.right == null) {
            return root.left == null && root.right == null;
        }
        queueL.offer(root.left);
        queueR.offer(root.right);
        while (!queueL.isEmpty()) {
            TreeNode curL = queueL.poll();
            TreeNode curR = queueR.poll();

            if (curL.val != curR.val) {
                return false;
            }

            if (curL.right == null || curR.left == null) {
                if (curL.right != null || curR.left != null) {
                    return false;
                }
            } else {
                queueL.offer(curL.right);
                queueR.offer(curR.left);
            }
            if (curL.left == null || curR.right == null) {
                if (curL.left != null || curR.right != null) {
                    return false;
                }
            } else {
                queueL.offer(curL.left);
                queueR.offer(curR.right);
            }
        }
        return true;
    }
}